package arithmetic.demo18;

/**
 * 动态规划： 字符串区间dp + 分类讨论 ： 交错字符串
 */
class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {

        // 动态规划 + 分类讨论
        int len1 = s1.length(), len2 = s2.length(), len3 = s3.length();

        // 特殊情况处理
        if(len1 + len2 != len3 ) {
            //如果两个长度都加起来都不等于 s3
            return false;
        }

        // 创建 dp
        boolean[][] dp = new boolean[len1+1][len2 + 1];

        // 初始化
        s1 = " " + s1;
        s2 = " " + s2;
        s3 = " " + s3;

        // 左上角首元素
        dp[0][0] = true;

        // 转化为字符数组操作
        char[] str1 = s1.toCharArray();
        char[] str2 = s2.toCharArray();
        char[] str3 = s3.toCharArray();


        // 第一行初始化
        for(int j = 1; j <= len2; j++) {
            // 如果相等位置相等说明是可以拼接
            if(str2[j] == str3[j]) {
                dp[0][j] = true;
            } else {
                break;
            }
        }

        for(int i = 1; i <= len1; i++) {
            // 第一列初始化
            if(str1[i] == str3[i]) {
                // 如果第一列同一位置相等也是可以拼接的
                dp[i][0] = true;
            } else {
                break;
            }
        }


        // 自上而下， 自左而右填表
        for(int i = 1 ; i <= len1 ; i++) {
            for(int j = 1; j <= len2; j++) {
                // 如果相等就看前面的位置
                // 进入才更新， 不然会因为重复更新出现 bug
                if(str1[i] == str3[i + j] && dp[i-1][j]) {
                    dp[i][j] = true;
                } else if(str2[j] == str3[i + j] && dp[i][j-1]) {
                    dp[i][j] = true;
                }
            }
        }

        // 确定返回值
        return dp[len1][len2];

    }
}

/**
 * 简化版：交错字符串
 */

class Solution1 {
    public boolean isInterleave(String s1, String s2, String s3) {

        // 动态规划 + 分类讨论
        int len1 = s1.length(), len2 = s2.length(), len3 = s3.length();

        // 特殊情况处理
        if(len1 + len2 != len3 ) {
            //如果两个长度都加起来都不等于 s3
            return false;
        }

        // 创建 dp
        boolean[][] dp = new boolean[len1+1][len2 + 1];

        // 初始化
        s1 = " " + s1;
        s2 = " " + s2;
        s3 = " " + s3;

        // 左上角首元素
        dp[0][0] = true;

        // 转化为字符数组操作
        char[] str1 = s1.toCharArray();
        char[] str2 = s2.toCharArray();
        char[] str3 = s3.toCharArray();


        // 第一行初始化
        for(int j = 1; j <= len2; j++) {
            // 如果相等位置相等说明是可以拼接
            if(str2[j] == str3[j]) {
                dp[0][j] = true;
            } else {
                break;
            }
        }

        for(int i = 1; i <= len1; i++) {
            // 第一列初始化
            if(str1[i] == str3[i]) {
                // 如果第一列同一位置相等也是可以拼接的
                dp[i][0] = true;
            } else {
                break;
            }
        }


        // 自上而下， 自左而右填表
        for(int i = 1 ; i <= len1 ; i++) {
            for(int j = 1; j <= len2; j++) {
                // 如果相等就看前面的位置
                // 进入才更新， 不然会因为重复更新出现 bug
                dp[i][j] = (str1[i] == str3[i+j] && dp[i-1][j]) ||
                        (str2[j] == str3[i+j] && dp[i][j-1]);
            }
        }

        // 确定返回值
        return dp[len1][len2];

    }
}

class Test {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.isInterleave("a", "", "aa"));
    }
}